import java.util.*;

public class map_set {
    //找到出现一次的元素(其他元素出现两次)
    //map解法
    public int singleNumber1(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()==1){
                return entry.getKey();
            }
        }
        return -1;
    }
    //集合解法
    public int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        for(int i = 0;i<nums.length;i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }
    //最佳解法:异或解法(a*b*a=a*a*b=b)
    public int singleNumber3(int[] nums) {
        int ret=0;
        for (int i = 0; i < nums.length; i++) {
            ret^=nums[i];
        }
        return ret;
    }
    //深度拷贝(创建一个新链表,新链表与原链表结构相同,地址不同)链表(链表由val\next\random三个域,random域存储随机指针)
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    //map法
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Map<Node,Node> map=new HashMap<>();
        Node cur = head;
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
    //迭代法(在原链表每个节点复制节点,将复制节点的next域和random域修改,将原链表拆分为两个链表)
    public Node copyRandomList2(Node head) {
        for(Node p = head; p != null; p = p.next.next)  //复制每个节点，并将原链表和复制链表连在一起。
        {
            Node q = new Node(p.val);
            q.next = p.next;
            p.next = q;
        }

        for(Node p = head; p != null; p = p.next.next)   //复制random指针
        {
            if(p.random != null)
                p.next.random = p.random.next;
        }

        //拆分两个链表，并复原原链表
        Node dummy = new Node(-1), cur = dummy;
        for(Node p = head; p != null; p = p.next)
        {
            Node q = p.next;
            cur = cur.next = q;
            p.next = q.next;
        }

        return dummy.next;
    }
    //jewels代表石头中宝石的类型，stones 代表你拥有的石头。stones中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    //字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set=new HashSet<>();
        for(int i =0;i<jewels.length();i++){
            set.add(jewels.charAt(i));
        }
        int ret=0;
        for(int i =0;i<stones.length();i++){
            if(set.contains(stones.charAt(i))){
                ret++;
            }
        }
        return ret;
    }
    //给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map=new HashMap<>();
        List<String> list=new ArrayList<>();
        for(int i = 0;i<words.length;i++){
            map.put(words[i],map.getOrDefault(words[i],0)+1);
        }
        PriorityQueue<Map.Entry<String,Integer>> pq=new PriorityQueue<Map.Entry<String,Integer>>(new Comparator<Map.Entry<String,Integer>>(){
            public int compare(Map.Entry<String,Integer> entry1,Map.Entry<String,Integer> entry2){
                return entry1.getValue()==entry2.getValue()?entry2.getKey().compareTo(entry1.getKey()):entry1.getValue()-entry2.getValue();
            }
        });
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            pq.offer(entry);
            if(pq.size()>k){
                pq.poll();
            }
        }
        while(pq.size()!=0){
            list.add(pq.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
    //坏键盘打字(str1为预期输出,str2为实际输出，输出大写坏掉的键盘(只有字母键坏掉)，函数输入保证至少一个坏掉)
    public static void func(String str1,String str2){
        Set<Character> set = new HashSet<>();
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        for(int i =0;i<str2.length();i++){
            set.add(str2.charAt(i));
        }
        Set<Character> setBroken = new HashSet<>();
        for(int i =0;i<str1.length();i++){
            char ch = str1.charAt(i);
            if(!set.contains(ch)&&!setBroken.contains(ch)){
                setBroken.add(ch);
                System.out.print(ch+"");
            }
        }

    }
    //出现第一个不重复的字符
    //哈希表做法
    public int firstUniqChar1(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i =0;i<s.length();i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for(int i =0;i<s.length();i++){
            if(map.get(s.charAt(i))==1){
                return i;
            }
        }
        return -1;
    }
    //数组做法(哈希表处理冲突的直接定制法)
    public int firstUniqChar2(String s) {
        int[] charNum=new int[26];
        for(int i =0;i<s.length();i++){
            charNum[s.charAt(i)-'a']++;
        }
        for(int i =0;i<s.length();i++){
            if(charNum[s.charAt(i)-'a']==1){
                return i;
            }
        }
        return -1;
    }
}
